Many electronic transactions, such as financial transactions, require security features to ensure that an authorized party securely transmits a communication to an authorized recipient. At a minimum, systems for supporting such transactions require privacy, data integrity, access control, and user nonrepudiation. The present invention is directed at the digital signatures used to provide user nonrepudiation. In a nutshell, user nonrepudiation means that a claim by a user that he/she was not responsible for a particular transaction can be refuted by proving that the user digitally signed the transaction document or message. As a result, given a secure digital signature method, users cannot repudiate the transactions they authorize or perform.
For the purposes of this document, the term "document" shall mean any message, file, or other grouping of electronically encoded information that is considered to be a single unit of information for purposes of applying a single digital signature to provide non-repudiation of the document being signed.
The term "digital signature" shall mean an electronically encoded string or label that can be non-reputably proven to have been generated with a particular signer's private key, with respect to a particular document. In other words, without having access to the signer's private key, it must be possible to prove that either (A) a specific document was signed with the signer's private key, or (B) that the specific document was not signed with the signer's private key (i.e., either the document signed is not the specific document, or the signature is not authentic).
The FSTC (Financial Services Technology Consortium) E-Check project (and many other systems) utilize the Digital Signature Standard for "signing" computerized (digital) documents, such as electronic checks (E-Checks). The DSS uses the public Digital Signature Algorithm (DSA) to compute various encryption key components and apply a digital "signature" to each signed document.
Referring to FIG. 1, a system that generates a digital signature 50 in accordance with the DSA utilizes three sources of inputs and various computational steps to generate a unique, "impossible to repudiate" signature for each document/individual signer pair. More specifically, a "digest" 51 of the document 52 to be signed is generated by applying a one-way hash function 54 known as the Secure Hashing Algorithm (SHA). A pseudo-random key k is generated by a procedure 56 sometimes known as the Step 1 procedure (also called the "Algorithm for Precomputing One or More k and r Values" in FIPS PUB 186, which is the official document describing DSS). The Step 1 procedure generates the key k as a function of a remembered internal state value 60 called KKEY, which is initially set to a seed value 58 when the Step 1 procedure is initialized. The KKEY value 60 is an internal state value of the Step 1 procedure that is generated each time a new pseudo-random key value k is generated. The digital signature 50 is generated by a predefined signature generation procedure 62 known as the Digital Signature Algorithm (DSA), as a function of the signer's private key x (64), the pseudo-random key k, and the digest 51 of the document produced by the SHA 54. Each DSS digital signature 50 generated by the sequence of procedures shown in FIG. 1 is of the form &lt;r,s&gt;: EQU &lt;r,s&gt;=&lt;(g.sup.k mod p) mod q, (k.sup..sup.-1 (H+xr)) mod q&gt;(Eq. 1)
where k is the pseudo-random key, x is the signer's private key, H is the digest of the document being signed, p is a prime number larger than 2.sup.511, q is a prime divisor of p-1 where 2.sup.159 &lt;q&lt;2.sup.160 (i.e,. (p-1)/q is equal to an integer), and g is an integer equal to h.sup.(p-1)/q mod p, where h is any integer between 1 and p-1 (i.e., 1&lt;h&lt;p-1) such that h.sup.(p-1)/q mod p&gt;1. p and q are sometimes called family parameters. The integers p, q and g can be public and can be common to a group of users.
In DSS, the signer's public key, y, is related to the signers private key by y=g.sup.x mod p.
In systems complying with the DSS, the pseudo-random key k, the document digest H and the signer's private key x are all 160 bit values. The KKEY value and its seed value are both 160 to 512 bit values, depending on the implementation. The original document can be any size, of course. The signer's private key x, by definition, must be highly unguessable, and the KKEY seed value must also be highly unguessable.
The term "a highly unguessable value" is defined to mean a value which is effectively unguessable, except by the brute force method of trying all possible values. In order for a value to be highly unguessable it must be (A) sufficiently random that there is no effective way to re-compute its value or the set of all possible values, or (B) "personalized," based on information or personal choices not known to anyone else. Also, for a value to be highly unguessable it must be securely stored or maintained so that it cannot be easily copied or stolen, and it must have a sufficiently long bit length that brute force attacks on the value are impractical. In other words, a 16 bit value cannot be considered to be unguessable, no matter how random, because it would take so few computations to try every possible value. Given continued exponential growth in computer power, the 160 bit length key values used in DSS are becoming less and less unguessable every year. The present invention assumes that the number of bits used in the DSS key values will be adjusted from time to time to preserve the unguessability of those values.
The uniqueness of each DSS signature guarantees both 1) the specific version and content of the document 52 that was signed, and 2) the identity of the individual who "signed" it. This is also done in such a way that any receiver of the signed document (if in possession of the "signer's Public Key") can verify both facts.
The strength of this "guarantee" relies on a couple of factors. First, the two key values (i.e., the private key x and the pseudo-random key k) used by the DSA to compute the signature must be kept highly secret. Second, the two key values must be difficult to determine (highly "unguessable") and unlikely to be common between any two users or documents (strong randomness or pseudo-randomness). Since the private key x is generally assumed to be different for each signer, care must be taken to ensure that the pseudo-random key k is different for every document signed by the same signer. Additional factors are the strength of both the DSA algorithm itself and also of another algorithm, SHA (Secure Hashing Algorithm), which is used to compute the document digest, which is a virtually unique "hash" total for the document being signed. The SHA algorithm is a public algorithm, as is DSA, so the strength of these algorithms does not rely on secrets in the computational aspects or algorithms themselves.
SHA uses no secret keys and, in fact, there is nothing "secret" about the answer it will compute. An important feature of SHA is that, given the same input document or character string to hash, it will always give the exact same answer, regardless of computer language or platform. Therefore, if two people want to ensure that they are both looking at the identical document which has an associated SHA hash total with it, they can compute the SHA hash total on their copy and ensure that it matches the expected result. Another important feature of SHA is that any change to the input document, including a single bit manipulation, will result in a different SHA hash result, indicating an altered document. This is a particularly important feature in using SHA to help ensure that E-Checks and other financially-based documents have not been tampered with or altered along the way.
The inclusion of the SHA hash result for a given document in the subsequent computation of the DSS digital signature therefore ensures that the signed document has not been altered in any way from what the originator (signer) generated. This addresses the first of the two guarantees: that the document received exactly matches the version and content of the document signed and sent.
The second of the guarantees, that the document has, in fact, been signed by the appropriate individual, is ensured by the inclusion of that individual's "Private Key" as another of the inputs to the DSA computation of the final signature. This Private Key (referred to as "x" in the Figures and elsewhere in this document), must be carefully chosen and protected. Keeping it "secret" is the primary protection over misuse.
In DSA, the individual's Private Key ("x"), the document's SHA-generated digest (sometimes denoted as "H" or "DocSHA"), and a pseudo-random key ("k"), are all used by the digital signature procedure to compute a completely unique digital signature each time. Since the algorithms used by the digital signal procedure are public, and the SHA hash value can be re-computed by anyone with access to the document, the additional application of the secret pseudo-random key "k" is critical to ensure the protection of the value of the individual's Private Key "x".